Virtually all complex integrated circuits are designed with the use of computer aided design (CAD) tools. Some CAD tools, called simulators, help the circuit designer verify the operation of a proposed circuit. Another type of CAD tool, called a silicon compiler (also sometimes known as automatic layout or place and route systems), generates the semiconductor mask patterns from a detailed circuit specification. Other CAD tools modify an existing circuit specification to optimize it for speed, layout area, or both.
Netlists
The detailed circuit specification used by silicon compilers, circuit simulators and other circuit design optimization tools is often called a netlist, and comprises a list of circuit components and the interconnections between those components. Circuit components are also known as "cells" where each cell in a specific circuit library has both a logical representation, as well as a circuit layout representation. A short netlist for a simple circuit is shown in Table 1.
TABLE 1 ______________________________________ Exemplary Netlist Cell Input Signals Output Signals Name 1 2 1 2 ______________________________________ XOR A B C XOR C CN1 Y AND A B CA AND C CN1 CB NOR CB CA CN ______________________________________
The netlist defines all of the interconnections between the components of the circuit. Each "signal" which interconnects two or more cells, or which represents an input or output for the entire circuit, is actually a node in the circuit which has been assigned a name. Thus the terms "signal" and "node" are often used interchangeably.
In the exemplary netlist shown in Table 1, signals A, B and CN1 are input nodes to the entire circuit, Y and CN are output nodes for the entire circuit, and nodes C, CA and CB are internal nodes.
In addition, the netlist specifies the nature of its components by specifying a cell name for each component. The cell name, in turn, specifies or points to a particular circuit in a predefined library of cells.
Circuits can also be represented by a list of statements in a Hardware Description Language (HDL), such as Verilog or VHDL. The HDL circuit description is then converted into a specific circuit netlist either by an engineer or by an HDL circuit synthesizer using a specified set of library cells.
Timing Constraints and Critical Paths
The problem that the present invention solves is as follows. An integrated circuit may have specified timing constraints, which define the maximum allowable amount of time that between receipt of a particular set of input signals and the generation of output signals on specified output nodes of the circuit. It is possible to determine from the circuit's netlist, and information in the cell library, whether or not the specified circuit will meet the specified timing constraints. In the prior art, if the circuit represented by a specified netlist does not meet the specified timing constraints, a circuit design engineer would have to analyze the circuit and attempt to modify either the circuit's netlist or the circuit's functional specification so that the modified circuit meets the specified timing constraints.
The present invention provides an automated methodology for modifying a circuit netlist so as to decrease the signal delays in critical timing paths of the circuit without changing the logical functions performed by the circuit. In many cases where the specified netlist fails to meet specified timing constraints by a small margin, the present invention will solve the timing problem without requiring an engineer to study and modify the circuit netlist.
Each gate or cell in a cell library is typically characterized by its area, function and timing. The area information in the cell library is used to estimate the total amount of silicon surface area that a specified circuit will occupy (i.e., by summing the individual cell areas and then adding space estimates for space occupied by cell interconnections).
The function information in the cell library is typically specified in terms of a boolean equation, as well as a specification of the number of input signals, output signals, power connections, and so on.
Computing Slack Values for Each Circuit Node.
The timing information in the cell library for a particular cell represents the timing delay from each input put to each output pin. A timing path between an input port land an output port j of a particular gate is approximated by a minimum gate propagation delay value Pij and a load dependent delay value Rij known as the ramp value. Each input port and each output port is also labeled by its capacitance C. The delay through a gate G from input port i to output port j is thus computed as follows: ##EQU1## where C.sub.x is the input capacitance of the x.sup.th gate driven by gate G, C.sub.r is a user specified routing capacitance representing an estimated capacitance of the gate's output node, C.sub.c is a user specified connection capacitance, and n is the number of input pods of other gates to which the gate output is connected.
In the preferred embodiment, the cell library provides two versions of each component: one with a single output drive and one with a double drive that is able to drive twice as many gates as the single drive cell.
The arrival time A of a generated signal at a node J of a circuit is computed as follows: EQU A(J)=MAX.sub.y.epsilon.i(J) (A(y)+(D(y,J))
where i(J) is the set of inputs to the cell or gate that generates the signal on node J and D(j,J) is the delay from input node y to node J. This computation starts at the input nodes and progresses toward the specified node J. Thus the computed arrival time for any specified node J is the worst case signal arrival time based on both a specified set of input signal times and the longest signal paths from the input nodes to node J.
The required time R at the same node J (i.e., the latest time at which the generated signal can arrive and meeting the specified timing requirements) is computed as follows: EQU R(J)=MAX.sub.z.epsilon.o(J) (R(z)+(D(z,J))
where o(J) is the set of nodes driven by a cell to which the signal on node J is an input. Thus required times are computed by working from the circuit's output nodes back toward the input nodes, and each node's required time is the earliest time required in order for the signal on the next successive node toward the output of the circuit to meet its timing requirements. The arrival times of signals at the circuit's inputs as well as the required times at the circuit's outputs are specified by the circuit designer. The required signal times and signal arrival times for the circuit's internal nodes are typically computed using the above equations.
The slack S(J) at each node J of the circuit is defined as the difference between the required time and the arrival time for that node: EQU S(J)=R(J)-A(J)
Thus, if the slack S(J) for a node is positive in value, the timing requirements of that node are satisfied. However, if the slack S(J) of a node is negative, that means that the circuit has a timing problem.
It is the goal of the present invention to identify circuit nodes having negative slack and to automatically modify the circuit netlist so that all circuit nodes have a non-negative slack value (i.e., greater than or equal to zero).